package week7;

/**
 * 279. 完全平方数
 * https://leetcode-cn.com/problems/perfect-squares/
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：22 ms, 在所有 Java 提交中击败了92.09% 的用户
 * 内存消耗：37.3 MB, 在所有 Java 提交中击败了80.43% 的用户
 * 通过测试用例：588 / 588
 * 炫耀一下:
 *
 *
 */
public class Week7PerfectSquares {

    public int numSquares(int n) {
        int[] array = new int[n + 1];
        for(int size = 1; size <= n; size++) {
            int min = Integer.MAX_VALUE;
            for(int perfect = 1; perfect * perfect <= size; perfect++) {
                min = Math.min(min, array[size - perfect * perfect]);
            }
            array[size] = min + 1;
        }
        return array[n];
    }

}
